package org.example.dp.unidimensional;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/10 14:26
 */

//如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
//
//
// 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
//
//
//
//
// 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
//
//
//
// 子数组 是数组中的一个连续序列。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3,4]
//输出：3
//解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
//
//
// 示例 2：
//
//
//输入：nums = [1]
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5000
// -1000 <= nums[i] <= 1000
//
//
// Related Topics 数组 动态规划 👍 567 👎 0
/**
 * @Description:
 *
 * 题解
 * 这道题略微特殊，因为要求是等差数列，可以很自然的想到子数组必定满足 num[i] - num[i-1]
 * = num[i-1] - num[i-2]。然而由于我们对于 dp 数组的定义通常为以 i 结尾的，满足某些条件的子数
 * 组数量，而等差子数组可以在任意一个位置终结，因此此题在最后需要对 dp 数组求和。
 *
 * @auther: wyatt
 * @date: 13:56 2024/5/13
*/
public class Solution413 {

    public static void main(String[] args) {
        Solution413 solution = new Solution413();
        int[] nums = new int[]{1,2,3,4};
        System.out.println(solution.numberOfArithmeticSlices(nums));
    }

    public int numberOfArithmeticSlices(int[] nums) {
        int size = nums.length;

        if(size < 3){
            return 0;
        }

        int[] dp = new int[size + 1];
        for(int i=2;i<size;i++){
            if( (nums[i] - nums[i-1]) == (nums[i-1] - nums[i-2])){
                dp[i] = dp[i-1] + 1;
            }
        }

        return Arrays.stream(dp).sum();
    }
}
